# 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
#
#  进阶：你能尝试使用一趟扫描实现吗？
#
#
#
#  示例 1：
#
#
# 输入：head = [1,2,3,4,5], n = 2
# 输出：[1,2,3,5]
#
#
#  示例 2：
#
#
# 输入：head = [1], n = 1
# 输出：[]
#
#
#  示例 3：
#
#
# 输入：head = [1,2], n = 1
# 输出：[1]
#
#
#
#
#  提示：
#
#
#  链表中结点的数目为 sz
#  1 <= sz <= 30
#  0 <= Node.val <= 100
#  1 <= n <= sz
#
#  Related Topics 链表 双指针
#  👍 1568 👎 0


from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


def log_list(h: ListNode):
    while h:
        log(h.val)
        h = h.next


def list_equity(h1: ListNode, h2: ListNode) -> bool:
    while h1 and h2:
        if h1.val != h2.val:
            return False
        h1 = h1.next
        h2 = h2.next
    if h1 is None and h2 is None:
        return True
    if h1 is None:
        return False
    if h2 is None:
        return False
    return True


"""
解1. 双指针
first 比 second 先出发n个节点
若原点出发, first 结束时, second为倒数第n个节点
若second从dummy出发, 则停在倒数第n的前驱

解2. 获取链表总长, 遍历找前驱删除
tips:
链表删除节点: 找到删除节点的前驱节点, 前驱节点指向后继节点
头节点没有前驱节点, 故引入dummy节点作为头节点的前驱节点

一共L个数, 倒数第n个数, 共需数: L-(n-1) = L - n + 1
倒数n的前驱: 数 L - n 
从0数n个数: for i in range(n)

解3. 栈, 全部入栈, 弹出n个, 找到前驱
"""
# 解1:获取链表总长, 遍历找前驱删除
# def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
#     list_len = 0
#     node = head
#     while node:
#         list_len += 1
#         node = node.next
#     dummy_node = ListNode(0, head)
#     curr = dummy_node
#     for i in range(list_len - n):
#         curr = curr.next
#     curr.next = curr.next.next
#     return dummy_node.next

# 解2: 双指针
# def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
#     dummy_node = ListNode(0, head)
#     first = head
#     second = dummy_node
#     for i in range(n):
#         first = first.next
#     while first:
#         first = first.next
#         second = second.next
#     second.next = second.next.next
#     return dummy_node.next


# 栈: 依次入栈, 弹出n个, 找到删除节点的前驱节点
# def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
#     dummy = ListNode(0, head)
#     curr = dummy
#     stack = list()
#     while curr:
#         stack.append(curr)
#         curr = curr.next
#     for i in range(n):
#         stack.pop()
#     prev = stack[-1]
#     prev.next = prev.next.next
#     return dummy.next


if __name__ == '__main__':
    s = Solution()
    # head = [1,2,3,4,5]
    # n = 2
    # [1,2,3,5]
    h1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    r1 = s.removeNthFromEnd(h1, 2)
    log_list(r1)
    e1 = ListNode(1, ListNode(2, ListNode(3, ListNode(5))))
    assert list_equity(r1, e1), r1
